package com.example.graph;

import java.util.*;

public class Interview04_01_FindWhetherExistsPath {
    public static void main(String[] args) {
        int[][] graph = {{0, 1}, {0, 2}, {1, 2}, {1, 2}};
        int[][] graph2 = {{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};

        // bfs
        System.out.println(findWhetherExistsPath(3, graph, 0, 2));
        System.out.println(findWhetherExistsPath(5, graph2, 0, 4));

        // dfs
        System.out.println(findWhetherExistsPath2(3, graph, 0, 2));
        System.out.println(findWhetherExistsPath2(5, graph2, 0, 4));


    }

    /**
     * 解法二:深度优先遍历(最优解)
     * @param n
     * @param graph
     * @param start
     * @param target
     * @return
     */
    public static boolean findWhetherExistsPath2(int n, int[][] graph, int start, int target) {
        // 构建邻接表
        Map<Integer, Set<Integer>> adj = buildAdjacencyList(graph);
        return dfsTraverse(adj, new boolean[n], start, target);

    }

    /**
     * 解法一:广度优先遍历
     * @param n
     * @param graph
     * @param start
     * @param target
     * @return
     */
    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 构建邻接表
        Map<Integer, Set<Integer>> adj = buildAdjacencyList(graph);
        return bfsTraverse(adj, n, start, target);

    }

    private static boolean bfsTraverse(Map<Integer, Set<Integer>> adj, int n, int start, int target) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n]; // 用于标记节点是否被访问过
        queue.offer(start);

        while (!queue.isEmpty()) {
            Integer tmp = queue.poll();
            if (tmp == target) {
                return true;
            }
            if (adj.get(tmp) != null) {
                Iterator<Integer> neighborIterator = adj.get(tmp).iterator();
                while (neighborIterator.hasNext()) {
                    Integer neighbor = neighborIterator.next();
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
        }

        return false;
    }

    private static boolean dfsTraverse(Map<Integer, Set<Integer>> adj, boolean[] visited, int start, int target) {
        if (start == target)
            return true;

        if (adj.get(start) != null) {
            Iterator<Integer> iterator = adj.get(start).iterator();
            while (iterator.hasNext()) {
                Integer tmp = iterator.next();
                if (!visited[tmp]) {
                    visited[tmp] = true;
                    if (dfsTraverse(adj, visited, tmp, target))
                        return true;
                }
            }
        }
        return false;
    }

    private static Map<Integer, Set<Integer>> buildAdjacencyList(int[][] graph) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            int from = graph[i][0];
            int to = graph[i][1];
            adj.computeIfAbsent(from, key -> (new HashSet<>())).add(to);
        }
        return adj;
    }
}
